package 中等.树;

import util.TreeNode;

/**
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应
 * 的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点
 * 的引用。
 * 一般来说，删除节点可分为两个步骤：
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/delete-node-in-a-bst
 */
public class 删除二叉搜索树中的节点_450 {

    public static void main(String[] args) {

        TreeNode node2 = new TreeNode(2);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        node2.left = node1;
        node2.right = node3;
        node3.right = node4;

        deleteNode(node2, 4);

    }

    /**
     * 二分查找要删除的节点
     * 1，如果当前节点的值比 key 小，那么往左子树找
     * 2，如果当前节点的值比 key 大，那么往右子树找
     * 3，如果当前节点的值等于 key
     * .    a 左子树为空，用右子树根节点代替当前节点
     * .    b 右子树为空，用左子树根节点代替当前节点
     * .    c 左右子树都不为空，
     * .        c1 为了不增加树的高度，选择右子树的最大值，或者左子树的最小值代替当前节点
     * .        c2 方便代码，直接将右子树放到，左子树的最小的下面
     *
     * @param root
     * @param key
     * @return
     */
    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root.val == key && root.left == null && root.right == null) return null;
        TreeNode curNode = root;
        TreeNode preNode = root;
        while (curNode != null) {
            if (curNode.val == key) {
                break;
            } else if (curNode.val > key) {
                preNode = curNode;
                curNode = curNode.left;
            } else {
                preNode = curNode;
                curNode = curNode.right;
            }
        }

        if (curNode == null) return root;

        if (curNode.left != null && curNode.right != null) {
            TreeNode tNode = curNode.right;
            while (tNode.left != null) tNode = tNode.left;
            tNode.left = curNode.left;

            curNode.val = curNode.right.val;
            curNode.left = curNode.right.left;
            curNode.right = curNode.right.right;
        } else if (curNode.left != null) {
            curNode.val = curNode.left.val;
            curNode.right = curNode.left.right;
            curNode.left = curNode.left.left;
        } else if (curNode.right != null) {
            curNode.val = curNode.right.val;
            curNode.left = curNode.right.left;
            curNode.right = curNode.right.right;
        } else if (preNode.left.val == key) {
            preNode.left = null;
        } else {
            preNode.right = null;
        }
        return root;
    }

}
